
#二分查找 被查找的列表必须是有序的 
#目标是查找对象所在的位置

import random

#我自己通过递归实现的
def binary_find(target,findList,st,et):           
    if st > et: return None        
    midIndex = int((st+et)/2)  
    midNum = findList[midIndex]    
    if target == midNum:        
        return midIndex
    elif target > midNum:        
        return binary_find(target,findList,midIndex+1,et)
    elif target < midNum:        
        return binary_find(target,findList,0,midIndex-1)


src = [7,20,40,5,70,90,10,30]
src.sort()
i = binary_find(100,src,0,len(src)-1)
print('i',i)

#，对于包含n个元素的列表，用二分查找最多需要log2n步
'''
对数 log₂8 = 3 意思是多少个2相乘等于8 
n个2相乘可以记作2的n次方 2ⁿ = 8 n = 3 对数就是求逆过程
对数是幂运算的逆运算

所以时间复杂度记作O(log n) log==log₂ 
时间复杂度指的是执行次数 而且指的是最差的情况

'''

#书里的代码
def binary_search(target,src):
    srcLen = len(src)
    low = 0
    high = srcLen - 1
    mid = int((low + high)/2)       
    while low<=high:
        mid = int((low + high)/2)
        guess = src[mid]        
        if target == guess:            
            return mid
        elif  target > guess: #查找目标在右边
            low = mid + 1
        elif target < guess: #查找目标在左边
            high = mid - 1
    return None

j = binary_search(90,src)
print("j=",j)